package 算法.字符串.LZW压缩算法;

import java.util.ArrayList;
import java.util.List;

import com.sun.org.apache.regexp.internal.recompile;

import util.LogUtils;
import edu.princeton.cs.algs4.BinaryStdOut;
import edu.princeton.cs.algs4.TST;
/**
 * 【LZW 压缩算法 】
 * 
 * @Date 2017-09-08 10：35
 * @author Administrator
 * @version
 */
public class LZW {
	private static final int R = 256;		//输入的字符串数
	private static final int L = 4096;		//编码总数=2^12
	private static final int W = 12;		//编码宽度
	
	private String[] rsCompress = new String[L];
	private List<Integer> rs = new ArrayList<Integer>();
	
	private void init() {
		int i = 0;
		for (i = 0; i < R; i ++) 
			rsCompress[i] = ""+ (char)i;
		rsCompress[R] = " ";				//文件结束标记（EOF）的前瞻字符
		for (int j = R+1; j < L; j ++) 
			rsCompress[j] = "";
	}
	
	public void compress() {
        String input = "ABRACADABRABRABRA";
        //三向单词查找树
		TST<Integer> st = new TST<Integer>();
		for (int i = 0; i < R; i ++) 
			st.put(""+(char)i, i);				//eg:K..'A', V..41
		int code = R + 1;						//R为文件结束(EOF)的编码
		while (input.length() > 0) {
			String curLongestPrefix = st.longestPrefixOf(input);
//			BinaryStdOut.write(st.get(curLongestPrefix), W);
			LogUtils.println("BinaryStdOut.write>>>", st.get(curLongestPrefix)); //输出curLongestPrefix的val
			rsCompress[st.get(curLongestPrefix)] = curLongestPrefix;
			rs.add(st.get(curLongestPrefix));
			
			//将curLongestPrefix和其后面一个字符合成的新key加入st
			int t = curLongestPrefix.length();			
			if(t<input.length() && code<L)	st.put(input.substring(0, t+1), code++); 
			input = input.substring(t, input.length());
		}
//		BinaryStdOut.write(st.get(R), W);
		LogUtils.println("BinaryStdOut.write>>>", R); //写入文件结束标志
//		BinaryStdOut.close();
	}
	
	public void expand() {
		for (int i = 0; i < L; i ++) {
			if(!rsCompress[i].equals(""))
				LogUtils.println("rs>>index"+i, rsCompress[i]);
		}
		
		int codeword = getCodeWord();
		String val = rsCompress[codeword];

		int i = R+1;
		//TODO:尚未理解，循环未终止。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
		while(true) {
			LogUtils.println("expand()>>val", val);
			codeword = getCodeWord();
			if (codeword == R)	break;
			String v = rsCompress[codeword];	//获取下一个编码
			//如果前瞻字符不可用
			if (i == codeword) 
				v = val + val.charAt(0);		//根据上一个字符串的首字母得到编码的字符串
			if (i < L)
				rsCompress[i++] = val + v.charAt(0);	//为编译表增加新条目
			val = v;									//更新当前编码
 		}
	}
	private int getCodeWord() {
		int codeword = rs.get(0);
		rs.remove(0);
		return codeword;
	}
	public static void main(String[] args) {
		LZW lzw = new LZW();
		lzw.init();
		lzw.compress();
		lzw.expand();
	}
	
}
